package _剑指offer._回溯;

import util.TreeNode;

/**
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * 题解：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yi-zhang-tu-rang-ni-ming-bai-shang-xia-jie-zui-da-/
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 二叉搜索树的特点：
 *      节点的左子树只包含小于当前节点的数。
 *      节点的右子树只包含大于当前节点的数。
 *      所有左子树和右子树自身必须也是二叉搜索树。
 * 
 * @author Liu Huan
 */

public class _98_验证二叉搜索树 {
    public static void main(String[] args) {
        Integer[] array = {2,1,3};
        TreeNode root = TreeNode.getTreeFromArray(array);
        System.out.println(isValidBST(root));
    }
    
    public static boolean isValidBST(TreeNode root) {
        return backTrack(root, null, null);
    }
    
    public static boolean backTrack(TreeNode root, Integer low, Integer high){
        if (root == null){
            return true;
        }
        
        int value = root.val;
        if (low != null && value <= low){
            return false;
        }
        if (high != null && value >= high){
            return false;
        }
        
        if (!backTrack(root.left, low, value)){
            return false;
        }
        if (!backTrack(root.right, value, high)){
            return false;
        }
        
        return true;
    }
}
